1. Field of Invention
Embodiments of the present invention relate, in general, to networking. More specifically, the embodiments of the present invention relate to methods and systems for fast and scalable implementation of packet-classification rules in a network based on meta-rules.
2. Description of the Background Art
In a typical network, packets are classified, in part, to ensure Quality of Service (QoS), and to provide differentiated services to classified flows. Information relevant for classifying a packet is contained in a plurality of distinct header fields in the packet. The header fields are the portion of the packet that precedes the body, which contains the data. The header fields also contain data, such as source and destination addresses User Datagram Protocol (UDP), destination port, payload type, sequence number, timestamp, and other such details about the packet as well as control and timing information that are needed for successful transmission across the network. Examples of header fields include, but are not limited to, version, traffic class, flow label, payload length, next header, hop limit, source address, and destination address.
Routers that provide service differentiation functionality use packet classification as one of the primary methods for identifying packet flows. Upon receipt of a packet, the router uses packet-classification rules to analyze the information available in packet header fields. Other network devices, such as firewalls, use packet classification to determine packets that can pass and packets that are blocked.
In one conventional classification method, an Access Control List (ACL) format is used for packet classification. The ACL format classifies a packet on the basis of the Internet Protocol (IP) header typically relying on multi-dimensional lookup algorithm. The ACL format comprises an ordered list of Access Control Entries (ACEs) with the header fields forming an ACE that is bound by logical operator ‘AND’. The process of using the ACL format is simple, as all the header fields forming the ACE are bound only by the logical operator ‘AND’.
In other classification methods, the header fields that define the packet-classification rules are bound by the logical operators AND, OR and NOT. Moreover, the header fields may not have a fixed position and may only be recognizable by keywords that precede header field values. This leads to an undefined structure with no pre-determined logical relation. The undefined structure of the packet-classification rules requires additional router resources to identify and to classify packets.
In another conventional classification method, rules used for classification are based on multiple header fields across the OSI layers and provide flexibility to the packet classification process. These complex packet-classification rules, often referred to as meta-rules, include rules that may have an undefined structure and can use any other rule as a variable. With meta-rules, it is possible to have multiple levels of nested rules. Regardless of the levels of nesting, the innermost rules are referred to as leaf rules that are typically structured rules in the ACL format. Other nested meta-rules may have an undefined structure and take the shape of arbitrary complex logical expressions on the header fields. The use of the meta-rules requires yet more router resources to identify and to classify packets thereby slowing down the packet classification process. This computational burden reduces the transfer rate of network traffic.
Some packet-classification languages support multiple levels of nested rules or meta-rules. Algorithms that are known in the art for solving logical expressions are generic and do not meet the speed requirement of packet classification algorithms in present-day network applications. What is required is a method for solving arbitrary logical expressions for fast and scalable packet classification in a network environment.